type instr = Cst(int) | Add | Mul | Var(int) | Pop | Swap
type instrs = list<instr>
type operand = int
type stack = list<operand>

let rec eval = (instrs: instrs, stk: stack) => {
  switch (instrs, stk) {
  | (list{Cst(i), ...rest}, _) => eval(rest, list{i, ...stk})
  | (list{Add, ...rest}, list{a, b, ...stk}) => eval(rest, list{a + b, ...stk})
  | (list{Mul, ...rest}, list{a, b, ...stk}) => eval(rest, list{a * b, ...stk})
  | (list{Var(i), ...rest}, _) => eval(rest, list{stk->List.getExn(i), ...stk})
  | (list{Pop, ...rest}, list{_, ...stk}) => eval(rest, stk)
  | (list{Swap, ...rest}, list{a, b, ...stk}) => eval(rest, list{b, a, ...stk})
  | (list{}, list{i, ..._}) => i
  | _ => assert false
  }
}
